<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html><head><title>Programming in Lua : 11.2</title>
<link rel="stylesheet" type="text/css" href="pil.css">
</head>
<body>
<p class="warning">
<A HREF="contents.html"><IMG TITLE="Programming in Lua (first edition)" SRC="capa.jpg" ALT="" ALIGN="left"></A>This first edition was written for Lua 5.0. While still largely relevant for later versions, there are some differences.<BR>The third edition targets Lua 5.2 and is available at <A HREF="http://www.amazon.com/exec/obidos/ASIN/859037985X/theprogrammil3-20">Amazon</A> and other bookstores.<BR>By buying the book, you also help to <A HREF="../donations.html">support the Lua project</A>.
</p>
<table width="100%" class="nav">
<tr>
<td width="10%" align="left"><a href="11.1.html"><img border="0" src="left.png" alt="Previous"></a></td>
<td width="80%" align="center"><a href="contents.html"><font face="Helvetica,Arial,sanserif">
<font color="gray">Programming in </font><font color="blue"> Lua</font>
</font></a></td>
<td width="10%" align="right"><a href="11.3.html"><img border="0" src="right.png" alt="Next"></a></td>
</tr>
<tr>
<td width="10%" align="left"></td>
<td width="80%" align="center"><a href="contents.html#P2">Part II. Tables and Objects</a>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
<a href="contents.html#11">Chapter 11. Data Structures</a></td>
<td width="10%" align="right"></td></tr>
</table>
<hr/>
<p><h2>11.2 &ndash; Matrices and Multi-Dimensional Arrays</h2>

<p>There are two main ways to represent matrices in Lua.
The first one is to use an array of arrays,
that is, a table wherein each element is another table.
For instance, you can create a matrix of zeros with
dimensions <code>N</code> by <code>M</code> with the following code:
<pre>
    mt = {}          -- create the matrix
    for i=1,N do
      mt[i] = {}     -- create a new row
      for j=1,M do
        mt[i][j] = 0
      end
    end
</pre>
Because tables are objects in Lua,
you have to create each row explicitly to create a matrix.
On the one hand, this is certainly more verbose than simply
declaring a matrix, as you do in C or Pascal.
On the other hand, that gives you more flexibility.
For instance, you can create a triangular matrix changing the
line
<pre>
      for j=1,M do
</pre>
in the previous example to
<pre>
      for j=1,i do
</pre>
With that code, the triangular matrix uses only half the memory
of the original one.

<p>The second way to represent a matrix in Lua is by composing the
two indices into a single one.
If the two indices are integers,
you can multiply the first one by a constant and then add
the second index.
With this approach,
the following code would create
our matrix of zeros with dimensions <code>N</code> by <code>M</code>:
<pre>
    mt = {}          -- create the matrix
    for i=1,N do
      for j=1,M do
        mt[i*M + j] = 0
      end
    end
</pre>

<p>If the indices are strings,
you can create a single index concatenating both indices
with a character in between to separate them.
For instance, you can index a matrix <code>m</code> with string indices
<code>s</code> and <code>t</code> with the code <code>m[s..':'..t]</code>,
provided that both <code>s</code> and <code>t</code> do not contain colons
(otherwise, pairs like (<code>"a:"</code>, <code>"b"</code>) and (<code>"a"</code>, <code>":b"</code>)
would collapse into a single index <code>"a::b"</code>).
When in doubt,
you can use a control character like `<code>\0</code>&acute;
to separate the indices.

<p><pre>

</pre>

<p>Quite often, applications use a <em>sparse matrix</em>,
a matrix wherein most elements are 0 or nil.
For instance, you can represent a graph by its adjacency matrix,
which has the value <code>x</code> in position <code>m,n</code> only when
the nodes <code>m</code> and <code>n</code> are connected with cost <code>x</code>;
when those nodes are not connected,
the value in position <code>m,n</code> is <B>nil</B>.
To represent a graph with ten thousand nodes,
where each node has about five neighbors,
you will need a matrix with a hundred million entries
(a square matrix with 10,000 columns and 10,000 rows),
but approximately only fifty thousand of them will not be <B>nil</B>
(five non-nil columns for each row,
corresponding to the five neighbors of each node).
Many books on data structures discuss at length
how to implement such sparse matrices without wasting 400 MB of memory,
but you do not need those techniques when programming in Lua.
Because arrays are represented by tables,
they are naturally sparse.
With our first representation
(tables of tables), you will need ten thousand tables,
each one with about five elements,
with a grand total of fifty thousand entries.
With the second representation,
you will have a single table,
with fifty thousand entries in it.
Whatever the representation,
you only need space for the non-nil elements.

<hr/>
<table width="100%" class="nav">
<tr valign="top">
<td width="90%" align="left">
<small>
  Copyright &copy; 2003&ndash;2004 Roberto Ierusalimschy.  All rights reserved.
</small>
</td>
<td width="10%" align="right"><a href="11.3.html"><img border="0" src="right.png" alt="Next"></a></td>
</tr>
</table>


</body></html>

